package cn.myworld.algorithm.opt;

import cn.myworld.algorithm.linear.Stack;

/**
 * 括号匹配问题
 */
public class BracketsMatch {

    public static void main(String[] args) {
        String str = "(])";
        boolean match = hot100(str);
        System.out.println(str + "中的括号是否匹配：" + match);
    }

    /**
     * 判断str中的括号是否匹配
     * @param str 括号组成的字符串
     * @return 如果匹配，返回true，反之返回false
     */
    public static boolean isMatch(String str) {
        // 1.创建栈对象，存储左括号
        Stack<String> chars = new Stack<>();
        // 2.从左往右遍历字符串
        for (int i = 0; i < str.length(); i++) {
            String currChar = str.charAt(i) + "";
            // 3.判断当前字符是否为左括号，如果是，则压栈
            if (currChar.equals("(")) {
                chars.push(currChar);
            } else if (currChar.equals(")")) {
                // 4.判断当前字符是否为右括号，如果是，则弹栈一个左括号，并判断弹出的结果是否为null，如果为null，证明没有匹配的左括号
                String pop = chars.pop();
                if (pop == null) {
                    return false;
                }
            }
        }
        // 5.判断栈中还有没有剩余的左括号，如果有，则证明括号不匹配
        if (chars.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }

    public static boolean hot100(String str) {
        // 1.创建栈对象，存储左括号
        Stack<String> chars = new Stack<>();

        // 2.从左往右遍历字符串
        for (int i = 0; i < str.length(); i++) {
            String pre = chars.isEmpty() ? "" : chars.peek();

            String currChar = str.charAt(i) + "";
            // 3.判断当前字符是否为左括号，如果是，则压栈
            if (currChar.equals("(") || currChar.equals("[") || currChar.equals("{")) {
                chars.push(currChar);
            } else if (currChar.equals(")") && pre.equals("(") || currChar.equals("]") && pre.equals("[") || currChar.equals("}") && pre.equals("{")) {
                // 4.判断当前字符是否为右括号，如果是，则弹栈一个左括号，并判断弹出的结果是否为null，如果为null，证明没有匹配的左括号
                String pop = chars.pop();
                if (pop == null) {
                    return false;
                }
            } else {
                return false;
            }
        }
        // 5.判断栈中还有没有剩余的左括号，如果有，则证明括号不匹配
        if (chars.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}
